package main.leetcode.clockin.March;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 57-II.和为s的连续正数序列
 *
 * <p>输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * <p>序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 * <p>
 *
 * <p>示例 1：输入：target = 9 输出：[[2,3,4],[4,5]]
 *
 * <p>示例 2：输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 * <p>限制：1 <= target <= 10^5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day6 {
    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new day6().findContinuousSequence(9)));
    }

    //  // 滑动窗口
    //  public int[][] findContinuousSequence(int target) {
    //    if (target == 1) return new int[][] {{1}};
    //    List<int[]> res = new ArrayList<>();
    //    int i = 1, j = 1, sum = 0, k;
    //    int[] tmp;
    //    while (i <= target / 2) {
    //      if (sum > target) sum -= i++; // 缩小窗口
    //      else if (sum < target) sum += j++; // 扩大窗口
    //      else { // 相等
    //        tmp = new int[j - i];
    //        for (k = i; k < j; k++) tmp[k - i] = k;
    //        res.add(tmp);
    //        sum -= i++; // 缩小窗口，从下一个数开始
    //      }
    //    }
    //    return res.toArray(new int[0][0]);
    //  }

    // 等差数列
    //    public int[][] findContinuousSequence(int target) {
    //        if (target == 1) return new int[][] {{1}};
    //        List<int[]> res = new ArrayList<>();
    //        int[] inner;
    //        int i, a, tmp;
    //        for (int n = 2; true; n++) {
    //            tmp = target - n * (n - 1) / 2;
    //            if (tmp % n == 0) { // tmp能被n整除，则a必为正数，因为tmp = n*a
    //                a = tmp / n;
    //                if (a > 0) {
    //                    inner = new int[n];
    //                    for (i = 0; i < n; i++) inner[i] = a + i;
    //                    res.add(inner);
    //                } else break;
    //            }
    //        }
    //        Collections.reverse(res);
    //        return res.toArray(new int[0][0]);
    //    }

    // 等差数列 + 一元二次方程
    //    public int[][] findContinuousSequence(int target) {
    //        if (target == 1) return new int[][] {{1}};
    //        List<int[]> res = new ArrayList<>();
    //        int[] inner;
    //        double tmp;
    //        int y = 2, x, k;
    //        while (y < target / 2 + 2) {
    //            tmp = (1 + Math.sqrt(Math.pow(2 * y + 1, 2) - 8 * target)) / 2;
    //            x = (int) tmp;
    //            if (x - tmp == 0) { // 确保x是整数
    //                inner = new int[y - x + 1];
    //                for (k = x; k <= y; ++k) inner[k - x] = k;
    //                res.add(inner);
    //            }
    //            ++y;
    //        }
    //        return res.toArray(new int[][] {});
    //    }

    // 先试2个连续数相加，此时是a+(a+1)。俩连续数相加和为target意味着target-1之后，可以整除2。
    // 如果可以被三个连续数相加，那么是a+(a+1)+((a+1)+1)，这就是在target减1之后，再减2，(即把第二项和第三项此时多出来的1减掉)，这时可以整除3，并且除3得到的数就是起始数字。
    // 如果可以被4个连续数相加得到，此时把target再减去3，重复以上步骤。
    // 不能整除就是说不能由i个连续数相加得到。
    // 可以把数字想象成一个个杆，你做不断削顶的操作，连续数的和为target的可以全部找出来
    public int[][] findContinuousSequence(int target) {
        if (target == 1) return new int[][] {{1}};
        List<int[]> res = new ArrayList<>();
        int[] inner;
        int i = 1; // 首尾间隔（或理解为序列长度）
        while (target > 0) {
            target -= i++;
            if (target > 0 && target % i == 0) {
                inner = new int[i];
                for (int j = target / i, k = 0; j < target / i + i; ++j, ++k) {
                    inner[k] = j;
                }
                res.add(inner);
            }
        }
        Collections.reverse(res);
        return res.toArray(new int[][] {});
    }
}
